home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 14055 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.2 KB
  1. Path: druid.borland.com!usenet
  2. From: pete@borland.com (Pete Becker)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: fast find algorithm
  5. Date: 11 Apr 1996 16:04:07 GMT
  6. Organization: Borland International
  7. Message-ID: <4kjahn$jp2@druid.borland.com>
  8. References: <Dp8wE6.8DG@cix.compulink.co.uk> <PdvZxMlyZE9U088yn@ime.usp.br> <4k9ggs$4ov@news1.mnsinc.com> <4kbrg8$luu@druid.borland.com> <316B2716.4993@airmail.net>
  9. NNTP-Posting-Host: pbecker.borland.com
  10. Mime-Version: 1.0
  11. Content-Type: Text/Plain; charset=ISO-8859-1
  12. X-Newsreader: WinVN 0.99.5
  13.  
  14. In article <316B2716.4993@airmail.net>, markn@airmail.net says...
  15. >
  16. >Pete Becker wrote:
  17. >> 
  18. >>     If you use a linked list at each array location to resolve conflicts 
  19. then
  20. >> you can delete elements.
  21. >
  22. >Knuth gives an algorithm for deleting elements from a table when using linear 
  23. pr
  24. >obing, 
  25. >and it's pretty easy to see how that would work.  I'm not sure there is a 
  26. practi
  27. >cal 
  28. >way to remove elements when using a secondary hash probe...
  29.  
  30. Good point: with linear probing you know where the next location is, and sooner 
  31. or later you know that you're done. My guess is that deleting would be constant 
  32. time in most cases, but O(n) worst case, where n is the size of the table.
  33.  
  34.